package com.cqs.leetcode.search;

import com.cqs.leetcode.TestCaseUtils;

import java.util.Random;


public class FindFirstandLastPositionElementinSortedArray34 {

    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) return new int[]{-1, -1};
        return searchRan(nums, target, 0, nums.length - 1);
    }

    private int[] searchRan(int[] nums, int target, int left, int right) {
        if (left > right) return new int[]{-1, -1};
        int mid = (right - left) / 2 + left;
        //这个分支是核心
        if (nums[mid] == target) {
            int[] leftResult = searchRan(nums, target, left, mid - 1);
            //将结果leftResult最小的有效值(最小的非-1值)赋值lIndex
            int lmin = leftResult[0] == -1 ? leftResult[1] : leftResult[0] ;
            int lIndex = lmin == -1 ? mid : lmin;
            int[] rightResult = searchRan(nums, target, mid + 1, right);
            //将结果leftResult最打的有效值(最小的非-1值)赋值rIndex
            int rIndex = rightResult[1] == -1 ? mid : rightResult[1];
            return new int[]{lIndex, rIndex};
        } else if (target < nums[mid]) {
            return searchRan(nums, target, left, mid - 1);
        } else {
            return searchRan(nums, target, mid + 1, right);
        }
    }

    public static void main(String[] args) {
//        int[] cases = TestCaseUtils.randomSortedArr(10, 10 / 2);
//        int[] cases = {1, 2, 3, 3, 4, 6, 8, 9, 9, 9, 10, 10, 11, 12, 13, 15, 15, 18, 19, 19};
        int[] cases = {0, 0, 1, 1, 2, 2, 2, 3, 3, 4};
        FindFirstandLastPositionElementinSortedArray34 find = new FindFirstandLastPositionElementinSortedArray34();
        int target = new Random().nextInt(cases.length / 2);
        target = 4;
        System.out.println("target:" + target);
        int[] ints = find.searchRange(cases, target);
        TestCaseUtils.print(cases);
        TestCaseUtils.print(ints);

    }
}
